// https://leetcode.cn/problems/minimum-window-substring/description/

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> tx(200), ts(200);
        for (auto x : t) tx[x]++;

        auto cover = [&]() -> bool {
            for (int i = 'a'; i <= 'z'; i++) 
                if (ts[i] < tx[i])
                    return false;
            
            for (int i = 'A'; i <= 'Z'; i++) 
                if (ts[i] < tx[i])
                    return false;

            return true;
        };

        int l = 0, r = 0, L = -1, R = s.size();
        string ans = "";
        while (r < s.size()) {
            ts[s[r]]++;
            while (cover()) {
                if (r - l + 1 < R - L + 1) R = r, L = l;
                ts[s[l]]--;
                l++;
            }
            r++;
        }
        if (L >= 0) ans = s.substr(L, R - L + 1);
        return ans; 
    }
};